// @algorithm @lc id=407 lang=cpp 
// @title trapping-rain-water-ii


// @test([[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]])=4
// @test([[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]])=10
// @test([[1,3,3,1,3,2],[3,2,1,3,2,3],[3,3,3,2,3,1]])=4
using pii = pair<int,int>;
class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        if(heightMap.size()<=2 || heightMap[0].size()<=2) return 0;
        int m = heightMap.size(), n = heightMap[0].size();
        vector<vector<bool>> via(m, vector<bool>(n, false));
        priority_queue<pii, vector<pii>, greater<pii>> water;
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                if(0==i||i==m-1||0==j||j==n-1){
                    water.push({heightMap[i][j], i*n+j});
                    via[i][j] = true;
                }
        int traped = 0;
        int dir[] = {-1, 0, 1, 0, -1};
        while(water.size()){
            int level = 0, idx = 0;
            tie(level, idx) = water.top(); water.pop();
            for(int d=0; d<4; d++){
                int i = idx / n + dir[d];
                int j = idx % n + dir[d+1];
                if(0<=i && i<m && 0<=j && j<n && !via[i][j]){
                    if(heightMap[i][j] < level)
                        traped += level - heightMap[i][j];
                    water.push({max(heightMap[i][j],level), i*n+j});
                    via[i][j] = true;
                }
            }
        }
        return traped;
    }
};